package 五排序;

import java.util.Arrays;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/18 9:27
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {

        int i = 10;
        int[] array = new int[i];
        //生成随机排序
        for (int k = 0; k < 10; k++) {

            for (int j = 0; j < i; j++) {
                array[j] = (int) (Math.random() * i * 10);
            }

            //原本数组：
            System.out.printf("第%d \t次数组=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }

            //开始排序
            //交换法
//            shellSort(array);
            //移动法
            quickSort(array, 0, array.length - 1);
            //输出
            System.out.printf("，排序后为=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            System.out.println();
        }

    }


    private static void quickSort(int[] array, int left, int right) {
        int r = right;
        int l = left;
        //记录一个中间值  用来判断数据是放在左边还是右边
        int pivot = array[(r + l) / 2];


        while (l <= r) {

            //从左边和右边依次往中间找 如果找到了就进行交换
            while (array[l] < pivot) {
                l++;
            }
            while (array[r] > pivot) {
                r--;
            }

            //交换
            if (l < r) {
                array[l] = array[l] + array[r];
                array[r] = array[l] - array[r];
                array[l] = array[l] - array[r];
            }


            //交换后发现当前的这个l值或者r的值和中间数相等
            //那么下次判断就不再判断这个l和r了 所以l++ 或r--；
            if (array[l] == pivot) {
                l++;
            }
            if (array[r] == pivot) {
                r--;
            }

        }


        //向左递归
        if (left < r) {
            quickSort(array, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(array, l, right);
        }

    }
}
